package com.changhong;

/**
 * Created by Administrator on 2018/12/13
 */
public class Heap001 {

    public static void main(String[] args) {
        int[] data = SortTools.genData(100);
//        int[] data = new int[] {10, 2, 8, 18, 5, 9, 20, 6, 3, 40};
        SortTools.print(data);
        sort(data);
        SortTools.print(data);
    }

    public static void sort(int[] data) {
        constructBigHeap(data);
        for (int i = data.length - 1; i > 0; i--) {
            SortTools.swap(data, 0, i);
            adjustHeap(data, 0, i);
        }
    }

    private static void constructBigHeap(int[] data) {
        for (int root = data.length / 2 - 1; root >= 0; root--) {
            adjustHeap(data, root, data.length);
        }
    }

    private static void adjustHeap(int[] data, int root, int length) {
        while (root < length && root <= length / 2 - 1) {
            int leftChild = 2 * root + 1;
            int rightChild = leftChild + 1;
            int maxChild = leftChild;
            if (rightChild < length && data[leftChild] < data[rightChild]) {
                maxChild = rightChild;
            }

            if (data[root] < data[maxChild]) {
                SortTools.swap(data, root, maxChild);
                root = maxChild;
            } else {
                break;
            }
        }
    }

}
